#include <iostream>
using namespace std;

/**
 * @brief 结点结构体
 * @param data 结点存储的数据
 * @param lChild 左孩子
 * @param rChild 右孩子
 */
typedef struct Node {
  int data;
  node lChild, rChild;
  Node() {}
  Node(int d) : data(d), lChild(nullptr), rChild(nullptr) {}
} Node, *node;

/**
 * @brief 初始化建立二叉排序树的方法
 *
 * @param a 数据源
 * @param len 数据源长度
 * @return node 返回的使树根结点
 */
node initBinarySortTree(int a[], int len) {
  node root = nullptr;
  for (int i = 0; i < len; ++i) {
    insertNode(root, a[i]);
  }
  return root;
}

/**
 * @brief 用于向二叉排序树中插入元素
 *
 * @param root 根节点
 * @param data 插入的值
 */
void insertNode(node root, int data) {
  // 如果当前节点是空，那么需要创建一个新的节点
  if (root == nullptr) {
    root = new Node(data);
    return;
  }
  if (data >= root->data) {
    if (root->rChild == nullptr) {
      node leaf = new Node(data);
      root->rChild = leaf;
    } else
      insertNode(root->rChild, data);

  } else {
    if (root->lChild == nullptr) {
      node leaf = new Node(data);
      root->lChild = leaf;
    } else
      insertNode(root->lChild, data);
  }
}

/**
 * @brief 删除节点
 *
 * @param root 父节点
 * @param data 要删除的节点的值
 */
void deleteNode(node root, int data) {}

void releaseNode(node root) {
  if (root->lChild == nullptr) {
  }
}